package q494_findTargetSumWays;

public class Solution {
    /**
     * 这道题和背包问题的关系比较难联系起来
     * 主要问题在于我们这里不是考虑背包能放的最大价值
     * 而是背包恰好能放这么多东西的组合数量
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 假设我们把数分成正负两组 left 与 right
        // l + r = sum
        // l - r = target
        // --> l = (sum + target)/2

        // 首先(sum + target) % 2 == 1意味着是无法凑出来这样的组合的
        // 如果Math.abs(target) > sum 也是无法凑出来的
        if ((sum + target) % 2 == 1 || Math.abs(target) > sum) {
            return 0;
        }

        // 显然如果target是负数并且绝对值比sum大，那在上一步已经pass
        // 所以left必然是一个正数
        int left = (sum + target) / 2;

        int[] dp = new int[left + 1];

        // 需要考虑初始化的一个问题
        // dp[0] 也就是背包的容量为0，那么有多少种组合数？答案是1，也就是不放东西，这也是一种组合数
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++) { // 遍历所有我们能用的数
            for(int j = left; j >= nums[i]; j--) {
                // 这里有较大的不同 我们考虑dp数组的意义：
                // 假设我们遍历到了一个num[i]这个数 那么考虑dp[j]代表的是在容量为j的情况下能够凑满的组合数
                // dp[j - nums[i]]也就是代表容量为j - nums[i]下的组合数
                // 显然 两者在遍历到num[i]这个数的时候就是累加的关系
                dp[j] = dp[j] + dp[j - nums[i]];
            }
        }

        return dp[left];
    }
}
